#include <iostream>
using namespace std;

int findKthNum(int A[], int sizeA, int B[], int sizeB, int k){
    // assume that size A > size B
    if(sizeA < sizeB){
        return findKthNum(B, sizeB, A, sizeA, k);
    }
    if(sizeB == 0)
        return A[k-1];
    if(k==1)
        return A[0] > B[0] ? B[0] : A[0];
    if(sizeA == 1){
        // here sizeB == 1 ad k ==2
        return A[0] > B[0] ? A[0] : B[0];
    }

    int pB = (k/2 -1) > (sizeB-1) ? (sizeB-1) : (k/2-1);
    int pA = k - 2 - pB;
    if(A[pA] > B[pB]){
        findKthNum(A, pA+1, B + pB + 1, sizeB - pB - 1, k - pB -1);
    }
    else if(A[pA] < B[pB]){
        findKthNum(A+pA+1, sizeA - pA - 1, B, pB+1, k - pA - 1);
    }
    else{
        return A[pA];
    }
}

double findMedianSortedArrays(int A[], int m, int B[], int n){
    int k = m + n;
    if(k%2 == 1){
        return findKthNum(A, m, B, n, k/2+1);
    }
    else{
        double sum = findKthNum(A, m, B, n, k/2);
        sum += findKthNum(A, m, B, n, k/2+1);
        return sum/2.0;
    }
}

double findMedianSortedArrays1(int A[], int m, int B[], int n) {
    // Start typing your C/C++ solution below
    // DO NOT write int main() function
    int aLeft = 0;
    int aRight = m;
    int bLeft = 0;
    int bRight = n;
    int size = m + n;
    if(m==0){
        if(n%2==0){
            return (B[n/2] + B[n/2-1])/2.0;
        }
        else{
            return B[n/2];
        }
    }
    if(n==0){
        if(m%2==0){
            return (A[m/2] + A[m/2-1])/2.0;
        }
        else{
            return A[m/2];
        }
    }
    if(A[aRight-1] <= B[bLeft]){
        double median;
        int midIndex = size/2;
        if(midIndex < m){
            median = A[midIndex];
        }
        else{
            median = B[midIndex-m];
        }
        if(size % 2 == 0){
            --midIndex;
            if(midIndex < m){
                median = (median + A[midIndex])/2.0;
            }
            else{
                median = (median + B[midIndex - m])/2.0;
            }
        }
        return median;
    }
    if(B[bRight-1] <= A[aLeft]){
        double median;
        int midIndex = size/2;
        if(midIndex < n){
            median = B[midIndex];
        }
        else{
            median = A[midIndex-n];
        }
        if(size % 2 == 0){
            --midIndex;
            if(midIndex < n){
                median = (median + B[midIndex])/2.0;
            }
            else{
                median = (median + A[midIndex-n])/2.0;
            }
        }
        return median;
    }
    // do the loop
    while(aLeft < aRight-1 || bLeft < bRight -1){
        int aMid = (aLeft+aRight-1)/2;
        int bMid = (bLeft+bRight-1)/2;
        if(A[aMid] == B[bMid]){
            return A[aMid];
        }
        else if(A[aMid] > B[bMid]){
            aRight = aMid;
            bLeft = bMid;
        }
        else{
            aLeft = aMid;
            bRight = bMid;
        }
    }
    if(size % 2 == 0){
        return (A[aLeft] + B[bLeft]) / 2.0;
    }
    else{
        return A[aLeft] < B[bLeft] ? B[bLeft] : A[aLeft];
    }

}



int main(){
    int a[3] = {1,2,0};
    int b[3] = {1,2,0};
    cout<<findMedianSortedArrays(a,2,b,2)<<endl;

    return 0;
}